#include "StdAfx.h"
#include "TestLink.h"
#include <stack>


TestLink::TestLink(void)
{

}


TestLink::~TestLink(void)
{

}

void TestLink::printNode(LinkNode* root){
	if(root == NULL){
		return;
	}
	while(root != NULL){
		cout<<root->data;
		root = root->next;
	}
	cout<<endl;
}

void TestLink::reversePrintRecursion(LinkNode* root){

	if(root != NULL){

		reversePrintRecursion(root->next);
		cout<<root->data;
	}
	
}

void TestLink::reversePrintMake(LinkNode* root){
	if(root == NULL || root->next == NULL){
		return;
	}
	LinkNode* tempNode = root;
	LinkNode* nowNode = root;
	LinkNode* preNode = NULL;

	while(tempNode->next != NULL){
		tempNode = tempNode->next;

		nowNode->next = preNode;

		preNode = nowNode;
		nowNode = tempNode;
	}
	nowNode->next = preNode;
	root = nowNode;
	printNode(nowNode);
}

void TestLink::reversePrintStack(LinkNode* root){
	if(root == NULL){
		return;
	}
	stack<LinkNode*> s;
	while(root != NULL){
		
		s.push(root);
		root = root->next;
	}
	
	while(!s.empty()){
		
		cout<<s.top()->data;
		s.pop();
	}
	cout<<endl;
}

void TestLink::mergeLink(LinkNode* root1,LinkNode* root2){

	if(root1 == NULL || root2 == NULL){
		return;
	}
	LinkNode* tempNode1;
	LinkNode* tempNode2;

	LinkNode* pHead;

	if(root1->data > root2->data){
		tempNode1 = root1;
		root1 = root2;
		root2 = tempNode1;
	}
	pHead = root1;
	tempNode1 = root1;
	tempNode2 = root2;

	while(tempNode1 != NULL && tempNode2 != NULL){
		root1 = tempNode1;

		while(tempNode1->next!= NULL && tempNode1->next->data<tempNode2->data){
			root1 = root1->next;
			tempNode1 = tempNode1->next;
		}

		while(tempNode2->next!= NULL && tempNode1->next!= NULL && tempNode2->next->data<tempNode1->next->data){
			tempNode2 = tempNode2->next;
		}

		tempNode1 = tempNode1->next;

		root1->next = root2;
		root2 = tempNode2->next;
		tempNode2->next = tempNode1;
		
		tempNode2 = root2;
	}

	if(tempNode2!= NULL){
		root1->next = root2;
	}

	printNode(pHead);
}
